//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/lexer/sm.h"
#include "sagittarius/io/io.h"
#include <malloc.h>
#include <string.h>

#if 0
sm_tier_type sm_get_num_byte_shifts(LXAlphaType a) {
    #if !SAGITTARIUS_LXALPHA_USE_GMP
    sm_tier_type n=0;
    for(;n<4;++n) {
        if(a & 0xff000000)
            return n;
        a <<= 8;
    }
    #else
    sm_tier_type n=0;
    LXAlphaType copy;
    LX_FORCE_INIT(copy);
    LX_ALPHA_SET(copy, a);
    while(!LX_CMPALPHA_EQ_SPC(copy, 0)) {
        mpz_tdiv_q_ui(copy, copy, 256);
    }
    #endif
}
#endif

sm_tier_type sm_new_tbl(sm_itable_branch* b) {
    //SG_WRITE(1, "sm_new_tbl\n");
    sm_itable_single* tmp;
    if(b->leafs) {
        tmp = malloc((b->n+1)*sizeof(sm_itable_single));
        memcpy(tmp, b->leafs, (b->n)*sizeof(sm_itable_single));
        free(b->leafs);
        b->leafs = tmp;
    } else {
        b->leafs = malloc((b->n+1)*sizeof(sm_itable_single));
    }
    //init itable
    memset(b->leafs[b->n].itbl, 0, SM_ITABLE_SIZE*sizeof(sm_itype));
    return b->n++;
}

sm_itable_branch* sm_create_branches(sm_tier_type n) {
    sm_itable_branch* b;
    b = malloc(n*sizeof(sm_itable_branch));
    memset(b, 0, n*sizeof(sm_itable_branch));
    return b;
}

sm_itable* sm_create_itable(sm_tier_type n) {
    sm_itable* tbl=malloc(sizeof(sm_itable));
    tbl->b = sm_create_branches(n);
    tbl->n = n;
    return tbl;
}

void sm_destroy_branch(sm_itable_branch* b) {
    free(b->leafs);
}

void sm_destroy_itable(sm_itable* tbl) {
    sm_tier_type n;
    for(n=0; n<tbl->n; ++n)
        sm_destroy_branch(&tbl->b[n]);
    free(tbl->b);
    free(tbl);
}

void sm_ttable_reconstruct_alpha(int fd, LXAlphaType* a, sm_tier_type n, sm_tier_type index, sm_tier_type tier, sm_itable* tbl) {
    //gets the table one tier up that this one is contained in
    sm_tier_type i, k;
    sm_itable_branch* b;
    sm_itable_single* l;
    LXAlphaType x;
    
    LX_FORCE_INIT(x);
    LX_ALPHA_SET_SPC(x, index);
    LX_ALPHA_LSHIFT_SPC(x, (8*(tier-1)));
    
    LX_ALPHA_ADD(*a, *a, x);
    
    LX_ALPHA_CLEAR(x);
    
    if(tier != tbl->n) {
        b = &tbl->b[tier]; //next tier
        for(k=0; k<b->n; ++k) {
            l = &b->leafs[k];
            for(i=0; i<SM_ITABLE_SIZE; ++i) {
                if((l->itbl[i] & SM_ITABLE_EXISTS_FLAG) &&
                ((l->itbl[i] & SM_LOOKUP_MASK) == n)) {
                    uint32 s;
                    for(s=0; s<tier; ++s) {
                        SG_WRITE(fd, "  ");
                    }
                    SG_WRITE(fd, "Base at tier ");
                    sg_writeUInt64(fd, tier);
                    SG_WRITE(fd, " is ");
                    sg_writeUInt64(fd, n);
                    SG_WRITE(fd, " with index ");
                    sg_writeUInt64Hex(fd, index);
                    SG_WRITE(fd, "\n");
                    
                    sm_ttable_reconstruct_alpha(fd, a, k, i, tier+1, tbl);
                }
            }
        }
    } else {
        uint32 s;
        for(s=0; s<tier; ++s) {
            SG_WRITE(fd, "  ");
        }
        SG_WRITE(fd, "Base at top tier ");
        sg_writeUInt64(fd, tier);
        SG_WRITE(fd, " is ");
        sg_writeUInt64(fd, n);
        SG_WRITE(fd, " with index ");
        sg_writeUInt64Hex(fd, index);
        SG_WRITE(fd, "\n");
    }
}

sm_itype sm_ttable_fetch(LXAlphaType a, sm_itype tostate, sm_tier_type tier, sm_itable* tbl) {
    LXAlphaType tmp;
    //tier_type lookup;
    sm_tier_type index, leaf;
    index = LX_GET_FIXED_VALUE(a) & 0xFF;
    if(tier == tbl->n) {
        AT(tbl->b[tier-1].n == 1, "Wrong number of branches for root tier: should be 1");
        AT((LX_GET_FIXED_VALUE(a) & 0xFF) < SM_ITABLE_SIZE);
        leaf = 0 | SM_ITABLE_EXISTS_FLAG;
    } else {
        LX_FORCE_INIT(tmp);
        LX_ALPHA_SET(tmp, a);
        LX_ALPHA_RSHIFT_SPC(tmp, 8);
        
        leaf = sm_ttable_fetch(tmp, tostate, tier+1, tbl);
        LX_ALPHA_CLEAR(tmp);
    }
    AT(leaf & SM_ITABLE_EXISTS_FLAG);
    leaf = leaf & SM_LOOKUP_MASK; //now it can be used as an offset directly
    AT(leaf < tbl->b[tier-1].n, "Offset out of range");
    if(tier >= 2) {
        //non-terminal tier
        if(!(tbl->b[tier-1].leafs[leaf].itbl[index] & SM_ITABLE_EXISTS_FLAG)) {
            //doesn't exist: create a new table
            /*SG_WRITE(1, "sm_ttable_fetch: create new table at tier ");
            sg_writeUInt64(1, tier-1);
            SG_WRITE(1, " for leaf ");
            sg_writeUInt64(1, leaf);
            SG_WRITE(1, ", for index ");
            sg_writeUInt64(1, index);
            SG_WRITE(1, "\n");*/
            //create a new leaf in the tier below
            tbl->b[tier-1].leafs[leaf].itbl[index] = sm_new_tbl(&tbl->b[tier-2]) | SM_ITABLE_EXISTS_FLAG;
            return tbl->b[tier-1].leafs[leaf].itbl[index];
        } else {
            //already exists
            return tbl->b[tier-1].leafs[leaf].itbl[index];
        }
    } else {
        //terminal tier: no allocations
        tbl->b[tier-1].leafs[leaf].itbl[index] = tostate | SM_ITABLE_EXISTS_FLAG;
        return tbl->b[tier-1].leafs[leaf].itbl[index];
    }
}

void sm_dumpttable_leaf(int fd, sm_itable_single* l) {
    sm_tier_type i;
    for(i=0; i<SM_ITABLE_SIZE; ++i) {
        SG_WRITE(fd, "    Index[");
        sg_writeUInt64(fd, i);
        SG_WRITE(fd, "] -> 0x");
        sg_writeUInt64Hex(1, l->itbl[i]);
        SG_WRITE(fd, "\n");
    }
}

void sm_dumpttable_branch(int fd, sm_itable_branch* b) {
    sm_tier_type l; //leaf
    for(l=0; l<b->n; ++l) {
        SG_WRITE(fd, "  Transition table: Leaf ");
        sg_writeUInt64(fd, l);
        SG_WRITE(fd, "\n");
        sm_dumpttable_leaf(fd, &b->leafs[l]);
    }
}

void sm_dumpttable(int fd, sm_itable* tbl) {
    sm_tier_type t;
    for(t=0; t<tbl->n; ++t) {
        SG_WRITE(fd, "Transition table: Tier ");
        sg_writeUInt64(fd, t);
        SG_WRITE(fd, "\n");
        sm_dumpttable_branch(fd, &tbl->b[t]);
    }
}

void sm_dumpttable_symbols(int fd, sm_itable* tbl) {
    sm_tier_type n, i, t;
    sm_itable_branch* b = &tbl->b[0];
    sm_itable_single* l;
    LXAlphaType a;
    LX_FORCE_INIT(a);
    for(n=0; n<b->n; ++n) {
        l = &b->leafs[n];
        for(i=0; i<SM_ITABLE_SIZE; ++i) {
            if(l->itbl[i] & SM_ITABLE_EXISTS_FLAG) {
                for(t=1; t<tbl->n; ++t) {
                    LX_ALPHA_SET_SPC(a, 0);
                    SG_WRITE(fd, "Reconstructing symbol at ");
                    sg_writeUInt64Hex(fd, i);
                    SG_WRITE(fd, "...\n");
                    sm_ttable_reconstruct_alpha(fd, &a, n, i, 1, tbl);
                    SG_WRITE(fd, "Reconstructed symbol: ");
                    LX_WRITE_BUFL(fd, &a, 1);
                    SG_WRITE(fd, "\n");
                }
            }
        }
    }
    LX_ALPHA_CLEAR(a);
}

/// sm_do_ttable
sm_itable* sm_do_ttable(const dfaState* s) {
    LXAlphaType min, max, tmp;
    LXAlphaType tmpmin, tmpmax;
    LXAlphaType count;
    sm_tier_type n;
    sm_itable* tbl;
    RE_CharSetIter i;
    dfa_outTranLink *l=s->tbeg;
    if(!l || !l->cur)
        return NULL;
    LX_FORCE_INIT(min);
    LX_FORCE_INIT(max);
    LX_FORCE_INIT(tmp);
    LX_INIT_SET_SPC(count, 0);
    
    //initial
    re_CSlb(&min, l->cur->cs);
    re_CSub(&max, l->cur->cs);
    //l = l->next; //FIXED 08/13
    
    //get bounds
    while(l && l->cur) {
        //update lower bound
        re_CSlb(&tmp, l->cur->cs);
        if(LX_CMPALPHA_LT(tmp, min))
            LX_ALPHA_SET(min, tmp);
        //update upper bound
        re_CSub(&tmp, l->cur->cs);
        if(LX_CMPALPHA_GT(tmp, max))
            LX_ALPHA_SET(max, tmp);
        //update count
        re_CScount(&tmp, l->cur->cs);
        LX_ALPHA_ADD(count, count, tmp);
        /*SG_WRITE(1, "sm_do_ttable count: ");
        LX_ALPHA_WRITEINT(1, count);
        SG_WRITE(1, "\n");*/
        
        l = l->next;
    }
    
    LX_ALPHA_SUB(tmp, max, min);
    LX_ALPHA_INC(tmp); //because the bounds are inclusive
    /*SG_WRITE(1, "TranTable range = ");
    LX_ALPHA_WRITEINT(1, tmp);
    SG_WRITE(1, ":\n");
    lex_dumpDFAState(1, s);*/
    
    //Get root branch
    n=0;
    LX_FORCE_INIT(tmpmin);
    LX_FORCE_INIT(tmpmax);
    LX_ALPHA_SET(tmpmin, min);
    LX_ALPHA_SET(tmpmax, max);
    while(!LX_CMPALPHA_EQ(tmpmin, tmpmax)) {
        LX_ALPHA_RSHIFT_SPC(tmpmin, 8);
        LX_ALPHA_RSHIFT_SPC(tmpmax, 8);
        ++n;
    }
    if(n == 0) {
        /*SG_WRITE(1, "  Output code for single value: ");
        re_writeAlpha(1, tmpmin);
        SG_WRITE(1, "\n");*/
        tbl = NULL;
    } else {
        
        --n;
        /*SG_WRITE(1, "  Output starts at shift level: ");
        sg_writeUInt64(1, n);
        SG_WRITE(1, "\n");
        SG_WRITE(1, "  Number of characters: ");
        LX_ALPHA_WRITEINT(1, count);
        SG_WRITE(1, "\n");*/
        if(LX_GET_FIXED_VALUE(count) < 200) {
            //SG_WRITE(1, "  This state will use a table\n");
            tbl = sm_create_itable(n+1);
            sm_new_tbl(&tbl->b[n]);
            
            l=s->tbeg;
            while(l && l->cur) {
                if(!re_CSisEmpty(l->cur->cs)) {
                    i = re_CSIStart((RE_CharSet*)l->cur->cs);
                    do {
                        /*SG_WRITE(1, "    Do transitions for: ");
                        re_writeAlpha(1, RE_CSITER_GET(i));
                        SG_WRITE(1, "\n");*/
                        sm_ttable_fetch(RE_CSITER_GET(i), l->cur->s, 1, tbl);
                    } while(re_CSINext(&i));
                    RE_CSITER_CLEAR(i);
                }
                l = l->next;
            }
        } else {
            //SG_WRITE(1, "  This state will NOT use a table\n");
            tbl = NULL;
        }
        
        //sm_dumpttable(1, tbl);
        
        //sm_destroy_itable(tbl);
    }
    
    LX_ALPHA_CLEAR(min);
    LX_ALPHA_CLEAR(max);
    LX_ALPHA_CLEAR(tmpmin);
    LX_ALPHA_CLEAR(tmpmax);
    LX_ALPHA_CLEAR(tmp);
    LX_ALPHA_CLEAR(count);
    
    return tbl;
}

/// dfa2sm
smrep* dfa2sm(const dfarep* dfa) {
    //dfaState* s;
    uint32 n;
    smrep* sm;
    
    sm = LX_ALLOC(sizeof(smrep));
    sm->stbl = LX_ALLOC(dfa->n*sizeof(sm_itable*));
    sm->dfa = dfa;
    //sm->sf = malloc(dfa->n*sizeof(sm_stateformat);
    
    //s = dfa->s[0];
    for(n=0; n < dfa->n; ++n) {
        /*SG_WRITE(1, "Doing transition table for state ");
        sg_writeUInt64(1, n);
        SG_WRITE(1, "\n");*/
        sm->stbl[n] = sm_do_ttable(dfa->s[n]);
        //if(sm->stbl[n])
            //sm_dumpttable_symbols(2, sm->stbl[n]);
    }
    
    return sm;
}

void destroy_sm(smrep* sm) {
    size_t n;
    //free(sm->sf);
    for(n=0; n < sm->dfa->n; ++n) {
        if(sm->stbl[n])
            sm_destroy_itable(sm->stbl[n]);
    }
    LX_FREE(sm->stbl);
    LX_FREE(sm);
}
